<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>最短路径-Floyd</title>
  <script src="https://d3js.org/d3.v7.min.js"></script>
  <style>
    body {
      font-family: Arial, sans-serif;
    }
    .node {
      fill: #1f77b4;
      stroke: #fff;
      stroke-width: 2px;
    }
    .link {
      stroke: #999;
      stroke-width: 2px;
      stroke-opacity: 0.6;
    }
    .highlight {
      stroke: red;
      stroke-width: 3px;
    }
    .link-text {
      font-size: 12px;
      fill: #333;
      text-anchor: middle;
      pointer-events: none;
    }

    .path-sequence {
      font-size: 16px;
      margin-top: 20px;
    }
    .path {
      font-size: 16px;
      margin-top: 20px;
    }
    .message {
      font-size: 18px;
      font-weight: bold;
      color: red;
      margin-top: 20px;
    }
  </style>
</head>
<body>
  <h1>最短路径(Floyd算法)</h1>
  <svg width="800" height="600"></svg>
  <div id="message" class="message"></div>
  <div id="path-sequence" class="path-sequence"></div>
  <div id="path" class="path"></div>

  <script>
    // 随机生成图的函数
    function generateRandomGraph(nodeCount, edgeCount) {
  const nodes = [];
  const links = [];
  const nodeIds = "ABCDEF".split(""); // 使用A-F作为节点ID，确保图是联通的

  // 生成节点
  for (let i = 0; i < nodeCount; i++) {
    nodes.push({ id: nodeIds[i], x: Math.random() * 700 + 50, y: Math.random() * 500 + 50 });
  }

  // 生成边，确保图联通
  const requiredEdges = [
    { source: 0, target: 1, weight: 2 },
    { source: 1, target: 2, weight: 3 },
    { source: 2, target: 3, weight: 1 },
    { source: 3, target: 4, weight: 5 },
    { source: 4, target: 5, weight: 2 },
  ]; // 基础保证联通的边

  // 确保初始的联通边不重复
  const existingEdges = new Set();
  
  // 将初始的联通边加入到 existingEdges 中
  requiredEdges.forEach(edge => {
    const edgeId = `${Math.min(edge.source, edge.target)}-${Math.max(edge.source, edge.target)}`;
    existingEdges.add(edgeId);
  });

  // 添加随机边，直到生成所需的边数
  while (requiredEdges.length < edgeCount) {
    const sourceIndex = Math.floor(Math.random() * nodeCount);
    let targetIndex = Math.floor(Math.random() * nodeCount);
    
    // 确保源点和目标点不一样
    while (targetIndex === sourceIndex) {
      targetIndex = Math.floor(Math.random() * nodeCount);
    }
    
    // 确保这条边是唯一的，不重复添加
    const edgeId = `${Math.min(sourceIndex, targetIndex)}-${Math.max(sourceIndex, targetIndex)}`;
    if (existingEdges.has(edgeId)) {
      continue; // 如果边已经存在，跳过
    }
    
    existingEdges.add(edgeId);

    const weight = Math.floor(Math.random() * 10) + 1; // 权重随机值，1到10之间
    requiredEdges.push({ source: sourceIndex, target: targetIndex, weight });
  }

  // 将所有生成的边转化为链接
  requiredEdges.forEach(edge => {
    links.push({ source: nodes[edge.source], target: nodes[edge.target], weight: edge.weight });
  });

  return { nodes, links };
}

    // 获取Floyd算法的最短路径
function floyd(nodes, links, start, end) {
  const distances = {};
  const previous = {};
  
  // 初始化所有节点的距离为无穷大，上一节点为null
  nodes.forEach(node => {
    distances[node.id] = {};
    previous[node.id] = {};

    nodes.forEach(target => {
      if (node.id === target.id) {
        distances[node.id][target.id] = 0;  // 自己到自己的距离为0
        previous[node.id][target.id] = null;
      } else {
        distances[node.id][target.id] = Infinity;  // 默认其他节点的距离为无限大
        previous[node.id][target.id] = null;
      }
    });
  });

  // 初始化边的权重
  links.forEach(link => {
    distances[link.source.id][link.target.id] = link.weight;
    distances[link.target.id][link.source.id] = link.weight;  // 因为是无向图
    previous[link.source.id][link.target.id] = link.target.id;
    previous[link.target.id][link.source.id] = link.source.id;
  });

  // Floyd算法更新最短路径矩阵
  nodes.forEach(k => {
    nodes.forEach(i => {
      nodes.forEach(j => {
        if (distances[i.id][j.id] > distances[i.id][k.id] + distances[k.id][j.id]) {
          distances[i.id][j.id] = distances[i.id][k.id] + distances[k.id][j.id];
          previous[i.id][j.id] = previous[i.id][k.id];  // 更新路径
        }
      });
    });
  });

  // 回溯最短路径
  const path = [];
  let current = start;
  while (current !== end) {
    path.push(current);
    current = previous[current][end];
    if (current === null) {
      break; // 如果没有路径，提前退出
    }
  }
  if (current === end) {
    path.push(end);
  }

  return path;
}

// 创建图形和显示逻辑
const { nodes, links } = generateRandomGraph(6, 10);  // 随机生成6个节点和10条边
const svg = d3.select("svg");
const width = svg.attr("width");
const height = svg.attr("height");

// 创建力导向图
const simulation = d3.forceSimulation(nodes)
  .force("link", d3.forceLink(links).id(d => d.id).distance(150))
  .force("charge", d3.forceManyBody().strength(-500))
  .force("center", d3.forceCenter(width / 2, height / 2));

// 创建边（连线）
const link = svg.append("g")
  .selectAll(".link")
  .data(links)
  .enter().append("line")
  .attr("class", "link")
  .attr("stroke-width", 2)
  .on("mouseover", function(event, d) {
    d3.select(this).classed("highlight", true);
  })
  .on("mouseout", function(event, d) {
    d3.select(this).classed("highlight", false);
  })
  .on("click", function(event, d) {
    toggleEdgeSelection(d);
  });

// 添加权重文本到边上
svg.append("g")
  .selectAll(".link-text")
  .data(links)
  .enter().append("text")
  .attr("class", "link-text")
  .attr("x", d => (d.source.x + d.target.x) / 2)
  .attr("y", d => (d.source.y + d.target.y) / 2)
  .text(d => d.weight);

// 创建节点
const node = svg.append("g")
  .selectAll(".node")
  .data(nodes)
  .enter().append("circle")
  .attr("class", "node")
  .attr("r", 20)
  .attr("cx", d => d.x)
  .attr("cy", d => d.y);

// 创建节点的标签
svg.append("g")
  .selectAll(".node-label")
  .data(nodes)
  .enter().append("text")
  .attr("class", "node-label")
  .attr("x", d => d.x)
  .attr("y", d => d.y)
  .attr("dy", -25)
  .attr("text-anchor", "middle")
  .text(d => d.id);

// 用户选边和路径顺序
let userEdges = [];
let userPath = [];
let totalUserWeight = 0; // 用户选的路径总权重

// 计算正确路径
const correctPath = floyd(nodes, links, "A", "F");  // 计算从"A"到"F"的最短路径

    const correctPathWeight = correctPath.reduce((sum, nodeId, index) => {
      if (index === correctPath.length - 1) return sum;
      const source = nodeId;
      const target = correctPath[index + 1];
      const edge = links.find(link => (link.source.id === source && link.target.id === target) || (link.target.id === source && link.source.id === target));
      return sum + edge.weight;
    }, 0);

    console.log("Correct Path:", correctPath);
    console.log("Correct Path Weight:", correctPathWeight);

    // 显示正确的路径
    function displayCorrectPath() {
      const sequence = correctPath.slice(1).map((id, index) => {
        const source = correctPath[index];
        const target = id;
        const edge = links.find(link => (link.source.id === source && link.target.id === target) || (link.target.id === source && link.source.id === target));
        return `(${source} -> ${target}, weight: ${edge.weight})`;
      }).join(" -> ");
      document.getElementById("path-sequence").textContent = `正确路径之一: ${sequence}`;
    }
    displayCorrectPath();

    // 切换选中的边
        // 切换选中的边
       // 切换选中的边
function toggleEdgeSelection(edge) {
  const edgeId = `${edge.source.id}-${edge.target.id}`;
  const reverseEdgeId = `${edge.target.id}-${edge.source.id}`;

  // 判断边是否已被选择
  if (!userEdges.includes(edgeId) && !userEdges.includes(reverseEdgeId)) {
    userEdges.push(edgeId);
    totalUserWeight += edge.weight;
    userPath.push(edge.source.id);
    userPath.push(edge.target.id);
  }

  displayUserPath();
  validatePath();
}

// 显示用户选的路径
function displayUserPath() {
  const sequence = userEdges.map(edgeId => {
    const [source, target] = edgeId.split("-");
    const edge = links.find(link => (link.source.id === source && link.target.id === target) || (link.target.id === source && link.source.id === target));
    return `(${source} -> ${target}, weight: ${edge.weight})`;
  }).join(" -> ");
  document.getElementById("path").textContent = `你的路径: ${sequence}`;
}

// 验证用户选择的路径是否正确
// 验证用户选择的路径是否正确
    // 验证用户选择的路径是否正确
function validatePath() {
  // 检查路径头尾是否相接：前后两条边通过同一个点连接
  const userStartNode = userPath[0];
  const userStartNode2= userPath[1];
  const userEndNode = userPath[userPath.length - 1];
  const userEndNode2 = userPath[userPath.length - 2];

//   // 查找路径中相邻节点是否相接
//   let isConnected = false;
//   for (let i = 1; i < userPath.length; i++) {
//     const source = userPath[i - 1];
//     const target = userPath[i];

//     // 检查是否有边连接 source 和 target
//     const edge = links.find(link => (link.source.id === source || link.target.id === target) || (link.target.id === source || link.source.id === target));
//     if (edge) {
//       isConnected = true;
//     }
//   }

//   // 如果路径没有相接，提示错误
//   if (!isConnected) {
//     d3.select("#message").text("路径头尾不相接，重新开始!");
//     return;
//   }

  // 如果用户的路径已经到达 F，则判断路径总权重
  if ((userStartNode === "F" && userEndNode==="A")||((userEndNode === "F" || userEndNode2 === "F")&& (userStartNode ==="A"||userStartNode2 ==="A"))) {
    if (totalUserWeight === correctPathWeight) {
      d3.select("#message").text("恭喜！你找到了正确的最短路径！");
    } else {
      d3.select("#message").text("路径不正确，重新开始!");
    }
  }
}




    // 更新图形
    simulation.on("tick", () => {
      link
        .attr("x1", d => d.source.x)
        .attr("y1", d => d.source.y)
        .attr("x2", d => d.target.x)
        .attr("y2", d => d.target.y);

      node
        .attr("cx", d => d.x)
        .attr("cy", d => d.y);

      svg.selectAll(".node-label")
        .attr("x", d => d.x)
        .attr("y", d => d.y);

      // 更新权重显示位置
      svg.selectAll(".link-text")
        .attr("x", d => (d.source.x + d.target.x) / 2)
        .attr("y", d => (d.source.y + d.target.y) / 2);
    });

  </script>
</body>
</html>
